package problem135_Candy;

import java.util.Arrays;
import java.util.Comparator;

public class MySolution {
	public int candy(int[] ratings) {
		Child[] children=new Child[ratings.length];
		int[] canday=new int[ratings.length];
		for(int i=0;i<ratings.length;i++){
			children[i]=new Child(i,ratings[i]);
		}
		Arrays.sort(children,new Comparator<Child>(){
			@Override
			public int compare(Child o1, Child o2) {
				return Integer.compare(o1.rating, o2.rating);
			}
			
		});
		int sum=0;
		for(int i=0;i<children.length;i++){
			canday[children[i].id]=1;
			if(children[i].id>0&&children[i].rating>ratings[children[i].id-1]){
				canday[children[i].id]=canday[children[i].id-1]+1;
			}
			if(children[i].id<canday.length-1&&children[i].rating>=ratings[children[i].id+1]){
				canday[children[i].id]=Math.max(canday[children[i].id],canday[children[i].id+1]+1);
			}
			sum+=canday[children[i].id];
		}
		System.out.println(Arrays.toString(canday));
		return sum;
    }
	
	private class Child{
		int id;
		int rating;
		public Child(int id,int rating){
			this.id=id;
			this.rating=rating;
		}
	}
	
	public static void main(String[] args){
		System.out.println(new MySolution().candy(new int[]{1,2,2}));
	}
}
